/*
https://leetcode-cn.com/problems/expression-add-operators/solution/gei-biao-da-shi-tian-jia-yun-suan-fu-by-2o1s7/
 */
import java.util.ArrayList;
import java.util.List;

public class Solution282 {

    String num;
    int target;
    List<String> ans;
    List<String> result=new ArrayList<>();

    public List<String> addOperators(String num, int target) {
        this.num = num;
        this.target = target;
        this.ans = new ArrayList<>();
        StringBuffer expr = new StringBuffer();
        search(expr, 0, 0, 0);
        return result;
    }

    public void search(StringBuffer expr,int i,long res,long mul){
        if (i==num.length()){
            if (res==target){
                result.add(expr.toString());
            }
            return;
        }
        int length=expr.length();
        if (i>0){
            expr.append(0);
        }
        long val=0;
        for (int j = i; j < num.length() && (j == i || num.charAt(i) != '0'); j++) {
            val = val * 10 + num.charAt(j) - '0';
            expr.append(num.charAt(j));
            if (i == 0) {
                search(expr, j + 1, val, val);
            } else {
                expr.setCharAt(length, '+');
                search(expr, j + 1, res + val, val);
                expr.setCharAt(length, '-');
                search(expr, j + 1, res - val, -val);
                expr.setCharAt(length, '*');
                search(expr, j + 1, res - mul + mul * val, mul * val);
            }
        }
        expr.setLength(length);
    }


    public static void main(String[] args) {
        System.out.println(new Solution282().addOperators("00",0));
    }
}
